The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of elements including links (communication paths such as telephone or optical lines) and nodes (for example, routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
One class of routing protocol is the link state protocol. The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB), which is a map of the entire network topology, and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” (SPT) is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately. When there is a network change an LSP representing the change is flooded through the network by each node adjacent the change, each node receiving the LSP sending it to each adjacent node.
As a result, when a data packet for a destination node arrives at a node (the “first node”), the first node identifies the optimum route to that destination and forwards the packet to the next node along that route. The next node repeats this step and so forth.
It will be noted that in normal forwarding each node decides, irrespective of the node from which it received a packet, the next node to which the packet should be forwarded. In some instances this can give rise to a “loop”. In particular this can occur when the databases (and corresponding forwarding information) are temporarily de-synchronized during a routing transition, that is, where because of a change in the network, a new LSP is propagated that induces creating a loop in the RIB or FIB. As an example, if node A sends a packet to node Z via node B, comprising the optimum route according to its SPF, a situation can arise where node B, according to its SPF determines that the best route to node Z is via node A and sends the packet back. This can continue for as long as the loop remains although usually the packet will have a maximum hop count after which it will be discarded. Such a loop can be a direct loop between two nodes or an indirect loop around a circuit of nodes.
Another instance in which loops can occur is during a transition between topologies in a network supporting multi-topology routing. Multi-topology routing is described in “M-ISIS: Multi-topology routing in IS-IS” by T. Przygienda et al., which is available at the time of writing on the file “isis-wg-multi-topology-00.txt” in the directory proceedings/01mar/I-D” of the domain “IETF.org” of the world wide web. In multi-topology routing one or more additional topologies is overlaid on a base or default topology and different classes of data are assigned to different topologies. For example the base or default topology will be the entire network and an additional topology will be a subset of the default topology. It will be appreciated that the physical components of the network are common to both topologies but that for various reasons it may be desirable to assign certain classes of traffic to only a certain subset of the entire network as a result of which the multi-topology concept provides a useful approach to providing this functionality.
One example of the use of multiple topologies is where one class of data requires low latency links, for example Voice over Internet Protocol (VoIP) data. As a result such data may be sent preferably via physical landlines rather than, for example, high latency links such as satellite links. As a result an additional topology is defined as all low latency links on the network and VoIP data packets are assigned to the additional topology. Another example is security-critical traffic which may be assigned to an additional topology of non-radiative links. Further possible examples are file transfer protocol (FTP) or SMTP (simple mail transfer protocol) traffic which can be assigned to an additional topology comprising high latency links, Internet Protocol version 4 (IPv4) versus Internet Protocol version 6 (IPv6) traffic which may be assigned to different topologies or data to be distinguished by the quality of service (QoS) assigned to it.
Multi-topology routing can be performed in a strict or a preferred mode. In the strict mode a data packet must travel only over the assigned topology and otherwise be discarded, for example in the case of security critical traffic. In the preferred mode data packets are preferably sent over the assigned topology but may also pass through the default topology where there is no path using only the assigned topology; thus, the assigned topology is considered preferred, but not strictly required. However a constraint on preferred mode traffic is that once traffic enters its preferred topology it must travel exclusively over that topology to the destination and not reenter the default topology as otherwise looping could occur.
Problems can arise in multi-topology routing domains during transitions between topologies and in particular migrating packet classifications from one topology to another without packets looping. Such transitions can occur for example during introduction of a first or subsequent additional topology, the removal of a topology, the addition or removal of a class of data packets to or from an additional topology (other classes of data remaining within the topology) or changing a class of data between two additional topologies (other classes of data remaining within the existing topology).
In such cases, assuming that each topology is stable and loop free, a single hop loop can occur if a first router classifies a packet as belonging to a first topology and forwards it to a neighboring second router. If the second router then classifies the packet as belonging to another topology it may forward the packet back to the first router, both routers having computed the shortest route to the packet destination using a different set of metrics, each appropriate to the topology to which they classified the packet. It will be seen that such a situation could arise when a transition between topologies is taking place according to which some routers have implemented the transition and others have not. A multi-hop loop can also occur if the topologies use asymmetric metrics.
The situation can be further understood with reference to FIG. 1, which depicts an illustrative network diagram of a multi-topology routing domain. For purposes of visualization of the network the default network is shown in a first plane and the additional topology is shown superposed in a second parallel plane. However it will be appreciated that the default and additional topologies are in fact physically formed from the same physical components, sharing common nodes and links, each node being configured to forward data packets over either topology dependent on the classification of the data packet. Furthermore, for the purposes of comprehensibility, and in particular to allow distinction between multiple additional topologies, the topologies other than the default topology are assigned colors and the data to be carried by that topology identified by the same color. It will be appreciated that any appropriate nomenclature can be adopted and that any such nomenclature is used for the purposes of explanation only.
In the network shown in FIG. 1 nodes A, reference numeral 10, B, reference numeral 12, C, reference numeral 14 and D, reference numeral 16 comprise a fragment of a data communications network forming a default topology designated generally 18. A link 20 joins nodes A and B, a link 22 joins nodes B and C, a link 24 joins nodes C and D and a link 26 joins nodes A and D. All of the links have a cost 1 except for link 26 joining nodes A and D which has a cost 10.
An additional topology which may be denoted a “blue” topology 28 is defined sharing nodes A, B, C and D and the common links 20, 22, 24, 26 between them (denoted here 22′, 24′, 26′, 28′ for the purposes of clarity of illustration) and in the blue topology all the links have a cost 1 except for the link 20′ between nodes A and B which has a cost 10.
It will be seen, therefore, that the additional topology is effectively defined by identifying the links belonging to it and assigning appropriate costs, which may differ from the costs in other topologies. In normal operation, normal data will be forwarded along the default topology 18 and “blue” data (identified in a classification step) will be forwarded along the additional topology 28. However where the additional topology is, for example, being installed then a situation may arise where node B installs the new topology before node C. As a result node C will not recognize blue traffic as requiring a separate topology and will forward it towards a destination node A via the lowest cost route in the default topology, i.e. node B. However when the data packet arrives at node B this will recognize that it should be forwarded via the additional blue topology 28 and will recognize the shortest cost route to node A as being via node C. In this case node C will once again forward it to node B and it will be seen that a loop is set up. Until the network fully establishes the new additional topology, data will be lost and bandwidth unnecessarily consumed.